#include <iostream>
#include <list>
#include <cassert>

using namespace std;

// Structure to represent a memory block
struct MemBlock {
    size_t size;      // Size of the block in bytes
    bool free;        // True if the block is free, false if allocated
    MemBlock* prev;   // Pointer to the previous block
    MemBlock* next;   // Pointer to the next block
};

class MemoryPool {
private:
    size_t poolSize;           // Total size of the memory pool
    void* poolStart;           // Starting address of the memory pool
    MemBlock* freeListHead;   // Head of the free block list

    // Function to merge adjacent free blocks
    void mergeFreeBlocks(MemBlock* block) {
        if (block->next && block->next->free) {
            block->size += block->next->size;
            block->next = block->next->next;
            if (block->next) {
                block->next->prev = block;
            }
        }
        if (block->prev && block->prev->free) {
            block->prev->size += block->size;
            block->prev->next = block->next;
            if (block->next) {
                block->next->prev = block->prev;
            }
            block = block->prev; 
        }
    }

public:
    // Constructor to initialize the memory pool
    MemoryPool(size_t size) : poolSize(size), poolStart(malloc(size)), freeListHead(nullptr) {
        if (poolStart) {
            // Initialize the free list with a single block
            freeListHead = reinterpret_cast<MemBlock*>(poolStart);
            freeListHead->size = poolSize;
            freeListHead->free = true;
            freeListHead->prev = nullptr;
            freeListHead->next = nullptr;
        }
    }

    // Destructor to release the allocated memory
    ~MemoryPool() {
        free(poolStart);
    }

    // Allocate a block of memory from the pool
    void* allocate(size_t size) {
        // Find a suitable free block using first-fit allocation
        MemBlock* block = freeListHead;
        while (block) {
            if (block->free && block->size >= size + sizeof(MemBlock)) { 
                // Found a suitable block
                if (block->size >= size + 2 * sizeof(MemBlock)) {
                    // Split the block if enough space remains
                    MemBlock* newBlock = reinterpret_cast<MemBlock*>(reinterpret_cast<char*>(block) + sizeof(MemBlock) + size);
                    newBlock->size = block->size - size - sizeof(MemBlock);
                    newBlock->free = true;
                    newBlock->prev = block;
                    newBlock->next = block->next;
                    if (block->next) {
                        block->next->prev = newBlock;
                    }
                    block->next = newBlock;
                    block->size = size + sizeof(MemBlock); 
                } else {
                    // Otherwise, allocate the entire block (internal fragmentation)
                    block->free = false;
                }
                return reinterpret_cast<char*>(block) + sizeof(MemBlock);
            }
            block = block->next;
        }
        // No suitable block found
        return nullptr;
    }

    // Deallocate a previously allocated block
    void deallocate(void* ptr) {
        if (ptr) {
            MemBlock* block = reinterpret_cast<MemBlock*>(reinterpret_cast<char*>(ptr) - sizeof(MemBlock));
            assert(!block->free && "Error: Double free or corruption detected!");
            block->free = true;
            mergeFreeBlocks(block); // Merge with adjacent free blocks
        }
    }

    // Function to print the current state of the memory pool (for debugging)
    void printPoolState() {
        cout << "Memory Pool State:" << endl;
        MemBlock* block = freeListHead;
        while (block) {
            cout << "Block: Address=" << block << ", Size=" << block->size
                 << ", Free=" << (block->free ? "True" : "False") << endl;
            block = block->next;
        }
        cout << "--------------------" << endl;
    }
};

int main() {
    // Create a memory pool of 1024 bytes
    MemoryPool pool(1024);

    // Allocate and deallocate memory blocks
    void* ptr1 = pool.allocate(100);
    void* ptr2 = pool.allocate(250);
    pool.deallocate(ptr1); 
    void* ptr3 = pool.allocate(50); 
    pool.deallocate(ptr2);
    pool.deallocate(ptr3);

    // Print the state of the memory pool
    pool.printPoolState(); 

    return 0;
}